package Top101K;

/**
 * @Author quan
 * @Description 求最长公共子字符串
 * @Date 2023/10/26 10:22
 */
public class a03_LongestCommonStr {
    public static void main(String[] args) {

    }
    /**
     * 用二位数数组的方式求解
     */
    public static String getCommon(String str1, String str2){
        int end = 0;
        //1-创建一个二维数组
        int[][] arr = new int[str1.length()+1][str2.length()+1];
        //2-比较二维数组中的每个行和列的值是不是相等：如果不相等置为0，如果相等的话[i][j]位置的值=[i-1][j-1]+1
        int max = Integer.MIN_VALUE;
        arr[0][0] = 0;
        for (int i = 1; i < str1.length(); i++) {
            for (int j = 1; j < str2.length(); j++) {
                if(str1.charAt(i) == str2.charAt(j)){
                    arr[i][j] = arr[i-1][j-1]+1;
                }else{
                    arr[i][j] = 0;
                }
                //3-定义一个最大值max，如果[i][j]的值比max还大，就更新max
                if(arr[i][j] > max){
                    max = arr[i][j];
                    //4-在获取max值的时候的i值就是str1用subString的结束索引，开始索引就是end-max
                    end = i;
                }
            }
        }
        //注意：subString截取子字符串的时候，开始索引与结束索引，是左闭右开的。
        return str1.substring(end-max,end+1);
    }



//    abc, cdeabe 最长是ab
    //求两个字符串的最长公共字串
//    public static void main(String[] args) {
//        String str1 = "deabce";
//        String str2 = "abcedeabcefghk";
//        String res = getCommon(str1,str2);
//        System.out.println(res);
//    }
    /**
     * 自己的思路2，用例测试不完整通过
     */

//    public static String getCommon(String str1, String str2){
//        StringBuilder sb = new StringBuilder();
////        String res = "";
//        //1、遍历较短的字符串，依次减少短字符串的字符数量，判断长字符串是否包含该字串
//        //2、遍历字符串1，遇见与第二个字符串相等的字符开始计数，当前数量最大的字符串就是最长的公共字串
//        int count = 0;
//        int max = 0;
//        for (int i = 0; i < str1.length(); i++) {
//            for (int j = 0; j < str2.length(); j++) {
//                if(str1.charAt(i) == str2.charAt(j)){
//                    count++;
//                    if(count > max){
//                        max = count;
//                        sb.append(str1.charAt(i));
//                    }
//                    break;
//                }else{
//                    count = 0;
//                }
//            }
//        }
//        return sb.toString();
//    }
}
